package com.leetcode;

import java.util.*;

/**
 * Created by yijy on 2017/4/1.
 */
public class Solution1 {

    private static TreeNode root;
    private static TreeNode tree1;

    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        solution1.createTree();
        solution1.printTree(root);
        List<List<Integer>> level = solution1.levelOrder(root);
        for(int i=0;i<level.size();i++){
            for(int j=0;j<level.get(i).size();j++){
                System.out.print(level.get(i).get(j)+"\t");
            }
            System.out.println();
        }
        System.out.println();
        solution1.createTree1();
        List<Integer> integerList = solution1.preorderTraversal(tree1);
        for(int i=0;i<integerList.size();i++){
            System.out.print(integerList.get(i)+"\t");
        }

    }

    public void createTree(){
        root = new TreeNode(3);
        TreeNode root1 = new TreeNode(9);
        TreeNode root2 = new TreeNode(20);
        TreeNode root3 = new TreeNode(15);
        TreeNode root4 = new TreeNode(7);
        TreeNode root5 = new TreeNode(5);
        TreeNode root6 = new TreeNode(6);
        root.left = root1;
        root.right = root2;
        root1.left = root5;
        root1.right = root6;
        root2.left = root3;
        root2.right = root4;
    }

    public void createTree1(){
        tree1 = new TreeNode(3);
        TreeNode root1 = new TreeNode(1);
        TreeNode root2 = new TreeNode(2);
        tree1.right = root1;
        tree1.left = root2;
        root1.left = new TreeNode(3);
    }

    public void printTree(TreeNode root){
        if(root!=null){
            if(root.left!=null){
                printTree(root.left);
            }
            if(root.right!=null){
                printTree(root.right);
            }
            System.out.println(root.val);
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()) {
            int levelSize = q.size();
            List<Integer> currLevel = new ArrayList<>();
            for(int i = 0; i < levelSize; i++) {
                TreeNode currNode = q.poll();
                currLevel.add(currNode.val);
                if (currNode.left != null)
                    q.add(currNode.left);
                if (currNode.right != null)
                    q.add(currNode.right);
            }
            res.add(currLevel);
        }
        return res;
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node!=null){
                list.add(node.val);
                stack.push(node.left);
                stack.push(node.right);
            }
        }
        return list;
    }

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
}
